In the past, computers were primarily applied to processing rather mundane, repetitive numerical and/or textual tasks involving number-crunching, spread sheeting, and word processing. These simple tasks merely entailed entering data from a keyboard, processing the data according to some computer program, and then displaying the resulting text or numbers on a computer monitor and perhaps storing the results in a magnetic disk drive. However, today's computer systems are much more advanced, versatile, and sophisticated. Computers are now commonly called upon to render realistic computer-generated three-dimensional graphic images. This is accomplished by transforming real world three-dimensional objects into two-dimensional models having the illusion of depth. These models are then rendered by the computer for display onto a computer screen. Additional processing relating to color, lighting effects, textures, and depth comparisons are performed in order to render extremely realistic solid images. In the end, viewers are treated to highly realistic and visually stunning computer-generated displays. Some applications in which three-dimensional graphics play a vital role include computer-aided design and manufacture, special effects for movies, simulations, medical diagnostics, etc.
However, in some instances, it is preferable to display simple line drawings to better represent a particular three-dimensional object rather than the more sophisticated shaded surface representation. This is attributable to the fact that most people have familiarity and feel comfortable with working in terms of line drawings. For instance, when asked to draw a house, most people would draw the familiar figure of a triangle placed on top of a rectangle. Indeed, it is easier under certain circumstances for engineers and designers to visualize a simplified, streamlined line drawing instead of its corresponding shaded surface picture. Line drawings contain basic, artistically useful information. Often, particular aspects of a design or layout become more readily apparent in a line drawing as opposed to that of a solid surface representation.
Unfortunately, there is one major problem associated with line drawings. The problem is that displaying all of the lines associated with an object typically results in an overly crowded and oftentimes jumbled picture. This problem is especially acute for objects which happen to be complex in nature (e.g., a jet engine). As an example, FIG. 1(A) shows all of the lines corresponding to a simple line drawing of a house. In comparison, FIG. 1(B) shows the same line drawing, except that all "hidden" lines have been removed. This type of drawing is commonly referred to as a "hidden-line" rendering. Hence, displaying all of the lines is undesirable as it might actually serve to confuse the viewer. Removing the hidden lines makes it easier to recognize the shape or silhouette of an object.
Further exacerbating this problem relates to the way in which computers handle curved surfaces. Basically, a three-dimensional object is initially modeled as a "wire mesh" frame. The wire mesh frame is made up of a number of adjoining polygons (e.g., triangles). The polygons are defined by their vertices (e.g., a triangle is defined by its three vertices). Hence, an object can be moved, rotated, and scaled by merely manipulating the coordinates of the vertices corresponding to the polygons. Texture may then be mapped onto the polygons to give the object the appearance of solidity. With this type of polygonal graphics scheme, curved surfaces are modeled as a number of flat facets. The facets are comprised of one or more polygons. For example, FIG. 2(A) depicts how a cylinder is modeled by defining a number of facets. The two end caps are represented by a number of triangles. The cylindrical body is represented by adjoining facets in the shape of flat, long, rectangular strips, each of which is comprised of two triangles. Hence, in a standard line drawing, the edges of these facets are displayed. Displaying all facet edges tends to make line drawings even more cluttered and confusing. Consequently, an ideal hidden-line drawing would display only the visible real edges between distinct surfaces and the visible facet edges which are silhouette edges. A clearer hidden-line drawing of a cylinder is shown in FIG. 2(B). The two caps 201-202 correspond to real edges while lines 203-204 correspond to silhouette facet edges.
In the past, software have been developed which attempted to solve this problem. The software would take a given line drawing and proceed to eliminate superfluous lines in an effort to render a simpler, silhouette image. However, this approach suffers from several shortcomings. Namely, the resultant silhouette image was limited to a single point of view. If one were to view the generated silhouette image from a different viewpoint, it would be incorrect. This is due to the fact that the resultant silhouette image was generated based on a particular viewpoint. Straying from the initial point of view from which the silhouette image was generated results in greater and greater inaccuracies. Consequently, if a viewer desires to view the object from different angles, he or she must run the line drawing through the software algorithm for each and every different viewpoint. Since the software algorithm is rather lengthy and complex, having to run the software algorithm each time the viewpoint changes is time consuming, unwieldy, and frustrating.
Thus, there is a need for some method which is accurate and which also has the capability of interactively identifying and displaying only the true edges and silhouette edges of a line drawing which are also visible. The present invention provides an elegant solution which is fast, accurate, and relatively inexpensive to implement. As such, a graphics subsystem utilizing the present invention would have the ability to render smooth, highly accurate 3-D line drawings which only show visible silhouette images in real time, even in response to shifts in the viewpoint.